We study the problem of multi-robot target assignment to minimize the totaldistance traveled by the robots until they all reach an equal number of statictargets. In the first half of the paper, we present a necessary and sufficientcondition under which true distance optimality can be achieved for robots withlimited communication and target-sensing ranges. Moreover, we provide anexplicit, non-asymptotic formula for computing the number of robots needed toachieve distance optimality in terms of the robots' communication andtarget-sensing ranges with arbitrary guaranteed probabilities. The same boundsare also shown to be asymptotically tight. In the second half of the paper, we present suboptimal strategies for usewhen the number of robots cannot be chosen freely. Assuming first that alltargets are known to all robots, we employ a hierarchical communication modelin which robots communicate only with other robots in the same partitionedregion. This hierarchical communication model leads to constant approximationsof true distance-optimal solutions under mild assumptions. We then revisit thelimited communication and sensing models. By combining simple rendezvous-basedstrategies with a hierarchical communication model, we obtain decentralizedhierarchical strategies that achieve constant approximation ratios with respectto true distance optimality. Results of simulation show that the approximationratio is as low as 1.4.
展开▼
